import java.util.Map;

/**
 * Created by L.jp
 * Description:输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * User: 86189
 * Date: 2021-12-28
 * Time: 12:42
 */
//动态规划三部曲：
//    状态定义；求所有子数组和的最大值，也就是求以i下标结尾的子数组的最大和,dp[i]表示
//    状态转移:以i下标结尾的最大和，必须先求的i-1下标结尾的最大和，也就是用前i-1项的和+当前项再跟当前项比，取最大值
//    方程：dp[i]=max(dp[i-1]+array[i],array[i])
//    状态初始化：因为是连续的，所以必须要以第一个值作为初始值，dp[0]=array[0]
public class Solution {
    public static int FindGreatestSumOfSubArray(int[] array) {
        //法一：动归解法：
        /*
        if(array.length==1){
            return array[0];
        }
        //表示前i项连续数组的最大和
        int[] dp=new int[array.length];
        //状态初始化
        dp[0]=array[0];
        //最大值初始化
        int max=array[0];
        //遍历数组求出连续子数组的最大和，因为第一项已经给出，所以直接从数组第二项开始
        for(int i=1;i<array.length;i++){
            dp[i]=Math.max(dp[i-1]+array[i],array[i]);
            if(max<dp[i]){
                max=dp[i];
            }
        }
        return max;
        */
        //法二：由于dp[i]只跟dp[i-1]有关，所以可以优化，用一个total变量维护dp[i]的dp[i-1]的值
//        我们可以发现当前状态只跟上一个状态有关，所以我们可以只用一个int来代替dp数组，即total
//        如果total<0，那么这个时候就total=array[i]
//        如果total>0，那么就total=total+array[i]
//        然后实时跟max比较，更新最大值即可
        int total=0;//记录当前累计的和
        int max=array[0];
        //记住是求连续子数组的最大和
        for (int num:array) {
            total= Math.max(total+num,num);//试着去加上当前值，如果加上后比当前值小了，那么累计和就变成了num
            //或者
//            if(total<0){
//                total=num;//如果之前total累计的和>=0,说明当前数据+total，有利于整体增大
//            }else{
//                total+=num;//如果之前累计的和<0,说明当前数据+total，不利于整体增大,丢弃之前的所有值
//            }
            max=Math.max(total,max);//取得累计和跟max的最大值，不断更新
        }
        return max;

    }

    public static void main(String[] args) {
        int[] array={6,-3,-2,7,-15,1,2,2};
        System.out.println(FindGreatestSumOfSubArray(array));
    }
}
